package binary_search;

import java.util.Arrays;

public class BinarySearch {
    /*
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int mid = 0;
        while(low<=high){
            mid = (low+high) / 2;
            if(target<nums[mid]){
                high = mid-1;
            }else if(target > nums[mid]){
                low = mid+1;
            }else{
                return mid;
            }
        }
       return low;
    }
}
class FirstErr{
    /*
    你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
     */
    public boolean isBadVerSion(int n){
        return true;
    }
    public int firstBadVersion(int n) {
       int low = 1;
       int high = n;
       int mid = 0;
       while(low<=high){
           mid = low + (high-low)/2;
           if(!isBadVerSion(mid)){
               low = mid+1;
           }else if(isBadVerSion(mid)){
               high = mid - 1;
           }else{
               return mid;
           }
       }
       return low;
    }
}
class ChaoGuo{
    /*
    给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一次操作中，你可以删除 nums 中的最小元素。
你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。
示例 1：
输入：nums = [2,11,10,1,3], k = 10
输出：3
解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。
第二次操作后，nums 变为 [11, 10, 3] 。
第三次操作后，nums 变为 [11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。
示例 2：
输入：nums = [1,1,2,4,9], k = 1
输出：0
解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。
示例 3：
输入：nums = [1,1,2,4,9], k = 9
输出：4
解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。
     */
    public int minOperations(int[] nums, int k) {
        int count = 0;
        Arrays.sort(nums);
        int left  = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(k<=nums[mid]){
                right = mid - 1;
            }else if(k>nums[mid]){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return left;
    }
}
class Jvzhen{
    /*
    给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        int left = 0;
        int right = matrix[0].length - 1;
        int mid = 0;
        while(left<=right){
            if(i>=matrix.length){
                break;
            }
            if(target>matrix[i][matrix[0].length - 1]){
                i++;
                j=0;
                left = 0;
                right = matrix[0].length - 1;
                continue;
            }
            mid = left + (right - left) / 2;
            if(target>matrix[i][mid]){
                left = mid+1;
            }else if(target < matrix[i][mid]){
                right = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
}
class Solution{
    /*
    给你一个字符串 message 和一个正整数 limit 。
    你需要根据 limit 将 message 分割 成一个或多个 部分 。每个部分的结尾都是 "<a/b>" ，其中 "b" 用分割出来的总数 替换， "a" 用当前部分所在的编号 替换 ，编号从 1 到 b 依次编号。除此以外，除了最后一部分长度 小于等于 limit 以外，其他每一部分（包括结尾部分）的长度都应该 等于 limit 。
    你需要确保分割后的结果数组，删掉每部分的结尾并 按顺序 连起来后，能够得到 message 。同时，结果数组越短越好。
    请你返回 message  分割后得到的结果数组。如果无法按要求分割 message ，返回一个空数组。
    示例 1：
    输入：message = "this is really a very awesome message", limit = 9
    输出：["thi<1/14>","s i<2/14>","s r<3/14>","eal<4/14>","ly <5/14>","a v<6/14>","ery<7/14>"," aw<8/14>","eso<9/14>","me<10/14>"," m<11/14>","es<12/14>","sa<13/14>","ge<14/14>"]
    解释：
    前面 9 个部分分别从 message 中得到 3 个字符。
    接下来的 5 个部分分别从 message 中得到 2 个字符。
    这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。
    可以证明没有办法分割成少于 14 个部分。
    示例 2：

    输入：message = "short message", limit = 15
    输出：["short mess<1/2>","age<2/2>"]
    解释：
    在给定限制下，字符串可以分成两个部分：
            - 第一个部分包含 10 个字符，长度为 15 。
            - 第二个部分包含 3 个字符，长度为 8
     */
    public String[] splitMessage(String message, int limit) {
       return null;
    }

}
class Firsi_Last{
    /*
    给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
     */
    public int[] searchRange(int[] nums, int target) {
        int [] res = {-1,-1};
        int left = 0;
        int  right = nums.length - 1;
        int mid = 0;

        return res;
    }
}
class LuoXuan{
    /*
    整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
     */
        public int search(int[] nums, int target) {
            int res = -1;
            int l = 0;
            int r = nums.length - 1;;
            int index = 0;
            int temp = 0;
            boolean found = false;
            for(int i = 0;i<nums.length;i++,index++){
                if(nums[i]<nums[0]){
                    found = true;
                    break;
                }
            }
            if(!found){
                while(l<=r){
                    int mid = l + (r - l) / 2;
                    if(nums[mid]<target){
                        l = mid + 1;
                    }else if(nums[mid]>target){
                        r = mid - 1;
                    }else{
                        res = nums[mid] == target ? mid : -1;
                        break;
                    }
                }
            }else{
                if(target>nums[nums.length - 1]){
                    l = 0;
                    r = index - 1;
                    while(l<=r){
                        int mid = l + (r - l) / 2;
                        if(nums[mid]<target){
                            l = mid + 1;
                        }else if(nums[mid]>target){
                            r = mid - 1;
                        }else{
                            res = nums[mid] == target ? mid : -1;
                            break;
                        }
                    }
                }else{
                    l = index;
                    r = nums.length - 1;
                    while(l<=r){
                        int mid = l + (r - l) / 2;
                        if(nums[mid]<target){
                            l = mid + 1;
                        }else if(nums[mid]>target){
                            r = mid - 1;
                        }else{
                            res = nums[mid] == target ? mid : -1;
                            break;
                        }
                    }
                }
            }
            return res;
        }
}
class Find_smallest_luoxuan{
    /*
    已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
     */
    public int findMin(int [] nums){
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int mid = l + (r - l) /2;
            if(mid + 1 < nums.length && nums[mid] > nums[mid + 1])
                return nums[mid + 1];
            if(mid - 1 >= 0 && nums[mid] < nums[mid - 1])
                return nums[mid];
            if(nums[mid] > nums[r]){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return nums[l];
    }
}
class Find_min{
    /*
    给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = 0;
        int l2 = 0;
        int i = 0;
        int r1 = nums1.length - 1;
        int r2 = nums2.length - 1;
        int nums[] = new int [nums1.length + nums2.length];
        while(l1<=r1 && l2<=r2){
            if(nums1[l1]<nums2[l2]){
                nums[i] = nums1[l1];
                l1++;
                i++;
            }else{
                nums[i] = nums2[l2];
                l2++;
                i++;
            }
        }
        if(l1<=r1){
            for(;i<nums.length;i++){
                nums[i] = nums1[l1];
                l1++;
            }
        }
        if(l2<=r2){
            for(;i<nums.length;i++){
                nums[i] = nums2[l2];
                l2++;
            }
        }

        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right - left)/2;
        if(nums.length%2 == 0){
            return (double)(nums[mid] + nums[mid + 1]) / 2.0;
        }else{
            return nums[mid];
        }
    }
}
class Test{
    public static void main(String[] args) {
        Find_min findMin = new Find_min();
        int [] nums1 = {1,2};
        int [] nums2 = {3,4};
        double medianSortedArrays = findMin.findMedianSortedArrays(nums1, nums2);
    }
}

